package demo.practice.leetcode_eveyday;

import java.util.Arrays;
import java.util.Stack;

public class P628_2 {

    public static void main(String[] args) {
        P628_2 p628_2= new P628_2();
        p628_2.maximumProduct(new int[]{722,634,-504,-379,163,-613,-842,-578,750,951,-158,30,-238,-392,-487,-797,-157,-374,999,-5,-521,-879,-858,382,626,803,-347,903,-205,57,-342,186,-736,17,83,726,-960,343,-984,937,-758,-122,577,-595,-544,-559,903,-183,192,825,368,-674,57,-959,884,29,-681,-339,582,969,-95,-455,-275,205,-548,79,258,35,233,203,20,-936,878,-868,-458,-882,867,-664,-892,-687,322,844,-745,447,-909,-586,69,-88,88,445,-553,-666,130,-640,-918,-7,-420,-368,250,-786});
    }
    public int maximumProduct(int[] nums) {
//        Arrays.sort(nums); //-984 -960 999 969 951

        if(nums==null|| nums.length<3)
            return 0;
        Arrays.sort(nums);
        int len=nums.length;


        return Math.max(nums[len-3]*nums[len-2]*nums[len-1] ,nums[0]*nums[1]*nums[len-1] );

       /* if(nums==null|| nums.length<3)
            return 0;
        Stack<Integer> stack = new Stack<>();
        Stack<Integer> negative = new Stack<>();    //记录负数的最小两个

        for (int num : nums) {
            //单调栈，从大到小的顺序。然后如果栈size>3 弹出栈顶的
            pushSort(stack, num);
            if (stack.size() > 3)
                stack.pop();

            pushSortNegative(negative,num);
            if(negative.size()>2)
                negative.pop();

        }
        if(negative.size()==2){
            int bf=stack.pop()*stack.pop();
            int max=stack.pop();
            return  Math.max(max*negative.pop()*negative.pop(),max*bf );
        }
        return stack.pop()*stack.pop()*stack.pop();*/
    }


    private void pushSort( Stack<Integer> stack,int num ){
        if (stack.empty()) {
            stack.push(num);
            return;
        }
        if(stack.peek()<num){
            int top = stack.pop();
            pushSort(stack,num);
            stack.push(top);
        }else{
            stack.push(num);
        }


    }


    private void pushSortNegative( Stack<Integer> stack,int num ){
        if(num>=0)
            return;

        if (stack.empty()) {
            stack.push(num);
            return;
        }
        if(stack.peek()>num){ //当栈顶元素大于 目标元素，往下一层 压，这样栈  底从小  到大排列
            int top = stack.pop();
            pushSortNegative(stack,num);
            stack.push(top);
        }else{
            stack.push(num);
        }
    }




}
